1. Field of the Invention
The present invention relates to a first-in first-out storage device (this will be referred to as a FIFO in what follows) which sequentially stores data input from a write-side circuit and sequentially outputs the stored data to a read-side circuit in accordance with the order the data has been stored.
2. Description of Related Art
FIG. 1 is a block diagram showing the configuration of a conventional FIFO. This FIFO has a random access memory (RAM) 51 for temporarily storing data such that the time required to access a randomly selected datum does not depend on the time of the last access or the location of the most recently accessed datum, terminals 11, 12, 13, and 14 connected to a write-side circuit not shown in FIG. 1, a write counter 15, a full-state detection unit 16, terminals 21, 22, 23, and 24 connected to a read-side circuit not shown in FIG. 1, a read counter 25, and an empty-state detection unit 26.
Write-data WD to be stored in the RAM 51 is input from the write-side circuit to the terminal 11. A write control signal /WREQ ("/" indicates an inverted logic) is input to the terminal 12 from the write-side circuit. A write clock signal WCLK is input to the terminal 13 from the write-side circuit. The terminal 14 outputs a full-state signal FUL to the write-side circuit.
The terminal 21 outputs read data RDATA to the read-side circuit. A read control signal /RREQ is input to the terminal 22 from the read-side circuit. A read clock signal RCLK is input to the terminal 23 from the read-side circuit. The terminal 24 outputs an empty-state signal EMP to the read-side circuit.
The RAM 51 has a data terminal WD, a write control terminal /WE, a write address terminal WA, a read data terminal RD, and a read address terminal RA. The data terminal WD, write control terminal /WE, write address terminal WA, read data terminal RD, and read address terminal RA are connected to the terminals 11, 12, output-side terminal of the write-counter 15, terminal 21, and output-side terminal of the read-counter 25, respectively.
When the write control signal /WREQ input to the write control terminal /WE is a "L (LOW)" signal, that is, when the write-side circuit sends a write-instruction to the RAM 51, 1-word data input to the write data terminal WD is written in a storage region of the RAM 51 that corresponds to a write address WADR input to the write address terminal WA. The RAM 51 outputs the data stored in its storage region that corresponds to an address signal input to the read address terminal RA to the terminal 21 from the read data terminal RD. The RAM 51 has an 8-word storage region, for example, ranging from storage location 0 to storage location 7. By using storage location 0 to storage location 7 cyclically, the RAM 51 can hold up to 8-word data.
The write counter 15 has a clock terminal C connected to the terminal 13, an enable terminal /E connected to the terminal 12, and an output terminal connected to the input terminal of the full-state detection unit 16 and write address terminal WA of the RAM 51. When the write control signal /WREQ input to the enable terminal /E is an "L" signal, that is, when a write-instruction signal is input from the write-side circuit, the write counter 15 counts the write address WADR one by one in synchronization with the rise of the clock signal WCLK input from the clock terminal C and outputs the write address WADR from the output terminal. The write counter 15 outputs, for example, a write address WADR having one more bit than the number of bits required to represent the real address of the storage region of the RAM 51.
The read counter 25 has a clock terminal C connected to the terminal 23, an enable terminal /E connected to the terminal 22, and an output terminal for outputting counted values. The output terminal is connected to the input terminal of the empty-state detection unit 26, input terminal of the full-state detection unit 16, and read address terminal RA of the RAM 51. When the read control signal /RREQ input to the enable terminal /E is an "L" signal, that is, when a read-instruction signal is supplied to the read counter 25, the read counter 25 counts the write address RADR one by one in synchronization with the rise of the read clock signal RCLK input from the clock terminal C and outputs the read address RADR from the output terminal. The read counter 25 outputs, for example, a read address RADR having one more bit than the number of bits required to represent the real address of the storage region of the RAM 51.
The full-state detection unit 16 has two input terminals and one output terminal connected to the terminal 14. One of the two input terminals is connected to the output terminal of the write counter 15, and the other input terminal is connected to the output terminal of the read counter 25. The full-state detection unit 16 detects that the entire storage region of the RAM 51 is filled with effective data by comparing the write address WADR input from the write counter 15 with the read address RADR input from the read counter 25. Here, when the information of the bits of the write address WADR excluding its leading bit is identical to the information of the bits of the read address RADR excluding its leading bit, the storage region to be written next is the same as the storage region to be read next. In this case, if the information of the leading bit of the write address WADR differs from the information of the leading bit of the read address RADR, it means that the number of written data is larger than the number of read data. Hence, the full-state detection unit 16 detects that the entire storage region of the RAM 51 is filled with effective data and outputs a full-state signal FUL as an "H (HIGH)" signal.
The empty-state detection unit 26 has two input terminals and one output terminal connected to the terminal 24. One of the two input terminals is connected to the output terminal of the write counter 15, and the other input terminal is connected to the output terminal of the read counter 25. The empty-state detection unit 26 detects that the storage region of the RAM 51 has no effective data by comparing the write address WADR input from the write counter 15 with the read address RADR input from the read counter 25.
Here, when the information of the bits of the write address WADR excluding its leading bit is identical to the information of the bits of the read address RADR excluding its leading bit, the storage region to be written next is the same as the storage region to be read next. In this case, if the information of the leading bit of the write address WADR is identical to the information of the leading bit of the read address RADR, it means that the number of written data is equal to the number of read data. Hence, the empty-state detection unit 26 detects that the storage region of the RAM 51 has no effective data and outputs an empty-state signal EMP as an "H (HIGH)" signal.
Next, the basic operation of the conventional FIFO will be explained. When a write control signal /WREQ as an "L" signal, a write clock signal WCLK, and a write data signal WDATA are supplied from the write side circuit by a write operation of the write side circuit to the FIFO, the write counter 15 counts up the write address WADR. In addition, the RAM 51 stores the write data WDATA in the storage region that corresponds to the write address WADR that has already been output by the write counter 15.
On the other hand, when a read control signal /RREQ as a "L" signal and a read clock signal RCLK are supplied from the read-side circuit by the read operation of the read-side circuit, the read counter 15 counts up the read address RADR. In addition, the RAM 51 outputs as read data RDATA the data in the storage region that corresponds to the read address RADR that has already been output by the read counter 25. In this way, the stored data is output in accordance with the order the data has been stored.
The write operation is performed sequentially until the entire storage region of the RAM 51 is filled with data. When the entire storage region of the RAM 51 is filled with data, the information of all the bits but the leading bit of the write address WADR becomes identical to the information of all the bits but the leading bit of the read address RADR. The information of the leading bit of the write address WADR differs from the information of the leading bit of the read address RADR. Hence, the full-state detection unit 16 detects that the entire region of the RAM 51 is filled with effective data, and outputs a full-state signal FUL as an "H" signal. Thus, the full-state signal FUL as an "H" signal is output to the write side circuit via the terminal 14, and the write operation of the write side circuit is stopped.
The read operation is performed sequentially until the entire storage region of the RAM 51 becomes empty. When the entire storage region of the RAM 51 becomes empty, the information of all the bits of the write address WADR becomes identical to the information of all the bits of the read address RADR. The information of the leading bit of the write address WADR thus becomes equal to the information of the leading bit of the read address RADR. Hence, the empty-state detection unit 26 detects that the entire region of the RAM 51 has no data, and outputs an empty-state signal EMP as an "H" signal. Thus, the empty-state signal EMP as an "H" signal is output to the read side circuit via the terminal 24, and the read operation of the read side circuit is stopped.
However, the above-described conventional FIFO has the following problems. FIG. 2 is a time chart showing an exemplary operation sequence of the conventional FIFO. When the frequency or phase of the clock signal in accordance with which the write side circuit operates differs from the frequency or phase of the clock signal in accordance with which the read side circuit operates, the following problematic states are generated. As shown by line A in FIG. 2, the fall of the empty-state signal EMP is displaced from the rise of the read clock signal RCLK. As shown by line B in FIG. 2, the fall of the full-state signal FUL is displaced from the rise of the write clock signal WCLK. As shown by line C in FIG. 2, the pulse width is narrow and the fall of the empty-state signal EMP is displaced from the rise of the read clock signal RCLK.
As a result of these problematic states, the information contained in the full-state signal FUL is not properly transmitted to the write side circuit, and the information contained in the empty-state signal EMP is not properly transmitted to the read side circuit. For example, when the write side circuit has a set of multiple circuits which operate in parallel, if one circuit controls the restriction of the write operation in accordance with the full-state signal FUL and the other circuits cannot control the restriction of the write operation in accordance with the full-state signal FUL, this set of multiple circuits cannot operate in parallel.